package test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.*;

public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
  }

class Solution {
    public static int addTwoNumbers(String s) {
        if (s == null || s.length() == 0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int res = 0;
        int len = 0;
        int start = 0;
        for(int i = 0; i < s.length(); i++){
            if(map.containsKey(s.charAt(i)) && map.get(s.charAt(i)) >= start){
                start = map.get(s.charAt(i)) + 1;
            }
            len = i - start + 1;
            map.put(s.charAt(i),i);
            res = Math.max(res,len);
        }
        return res;
    }


    public static int reverse(int x) {
        Stack<Integer> stack = new Stack<Integer>();
        int absX=0;
        if(x<0){
            absX=Math.abs(x);
        }else{
            absX=x;
        }

        int result=0;
        char[] xChar=String.valueOf(absX).toCharArray();
        for(int i=0;i<(xChar.length)/2;i++){
            char temp=0;
            temp=xChar[i];
            xChar[i] = xChar[xChar.length-1-i];
            xChar[xChar.length-1-i] = temp;

        }
        try{
            result = Integer.parseInt(String.valueOf(xChar));
        }catch (Exception e){
            return 0;
        }
        if (x < 0 ){
            x = -1 * result;
            return x;
        }else {
            x = result;
            return x;
        }
    }

    public static void main(String[] args) {
         int[] ints={5,3,7,8,2,9,4,6};
        sort(ints,0,ints.length-1);
        System.out.print(ints);
    }

    public static int sort(int[] ints,int s,int e){

        if (s<e){
            int index=sortUnit(ints,s,e);
            sort(ints,0,index-1);
            sort(ints,index+1,e);

        }
        return s;
    }

    public static int sortUnit(int[] ints,int s,int e){
        int num=ints[s];
        int i=s;
        int j=e;
        while(i<j) {
            while (i < j) {
                if (ints[j] < num) {
                    ints[i] = ints[j];
                    break;
                }
                j--;
            }
            while (i < j) {
                if (ints[i] >= num) {
                    ints[j] = ints[i];
                    break;
                }
                i++;
            }
        }
        ints[i]=num;
        return i;

    }

















}